#include<bits/stdc++.h>
#define lowbit(x) (x&(-x))
using namespace std;
typedef long long ll;
const ll N = 2e5+10,INF = 1e18;
template <typename T> void tomin(T& x,T y){x = min(x,y);}
template <typename T> void tomax(T& x,T y){x = max(x,y);}
//
int T,n,a[N],b[N],tot;

ll tag;
struct BIT{
    int n; ll t[N];
    void init(int _n){
        n = _n;
        for(int i=1;i<=n;i++)t[i] = -INF;
    }
    void mdf(int x,ll v){
        for(;x<=n;x+=lowbit(x))tomax(t[x],v - tag);
    }
    ll qry(int x,ll S = -INF){
        for(;x;x-=lowbit(x))tomax(S,t[x]);
        return S + tag;
    }
}pre,suf; ll buc[N];

void solve(){
    cin>>n; tot = 0;
    for(int i=1;i<=n;i++)cin>>a[i],b[++tot] = a[i];
    sort(b+1,b+1+tot); tot = unique(b+1,b+1+tot)-b-1;
    for(int i=1;i<=n;i++)a[i] = lower_bound(b+1,b+1+tot,a[i])-b;
    //
    tag = 0; pre.init(tot+1); suf.init(tot+1); for(int i=0;i<=tot;i++)buc[i] = -INF; buc[0] = 0;
    pre.mdf(1,0); suf.mdf(tot+1,0);
    for(int i=2;i<=n;i++){
        ll val = max(pre.qry(a[i]),suf.qry(tot-a[i]));
        tomax(val,buc[a[i]] + tag + b[a[i]]);
        ll w = (a[i] == a[i-1]) * b[a[i]];
        tag += w; 
        if(buc[a[i-1]]+tag < val){
            buc[a[i-1]] = val-tag;
            pre.mdf(a[i-1]+1,val);
            suf.mdf(tot+1-a[i-1],val);
        }
    }
    ll ans = -INF; for(int i=0;i<=tot;i++)tomax(ans,buc[i] + tag);
    cout<<ans<<endl; 
}
int main(){
    freopen("color.in","r",stdin); freopen("color.out","w",stdout);
    ios::sync_with_stdio(false); cin.tie(0);

    cin>>T;
    while(T--)solve();

    return 0;
}